백준 1167번
오늘 풀어본 문제는 백준의 1167번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 $V$가 주어지고 $(2 \leq V \leq 100,000)$ 둘째 줄부터 $V$개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 $1$부터 $V$까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 $3$은 정점 $1$과 거리가 $2$인 간선으로 연결되어 있고, 정점 $4$와는 거리가 $3$인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 $-1$이 입력으로 주어진다. 주어지는 거리는 모두 $10,000$ 이하의 자연수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
풀이과정
첫 번째 시도
문제를 처음 읽었을 때, 트리의 지름이 무슨 개념인지 이해하는 데 조금 시간이 걸렸다. 내가 이해한 바로는, 트리 내부의 어떤 두 정점의 거리가 제일 멀 때, 그 두 정점 사이의 거리를 의미한다고 생각하였다.
해결 방법은, 아무 노드를 잡고, (나같은 경우는 $1$번 노드로 잡았다.) 가장 멀리 떨어진 노드를 찾은 뒤, 그 노드에서 다시 가장 멀리 떨어진 노드까지의 거리를 계산하는 것이다.
이러한 방법이 되는 이유를 나름대로 간단하게 생각해봤는데, 그건 처음 가장 멀리 떨어진 노드를 찾을 때는 전체 트리의 루트 노드를 기준으로 한쪽 subtree에서 가장 깊숙한 곳을 찾아낸 뒤, 그 다음 찾아내는 것이 반대편 subtree에서 가장 깊숙한 곳을 찾아낼 수 있기 때문에 작동할 것이라고 생각하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> graph(100001);
bool visited[100001] = { 0, };
int furthestNode = 0;
int furthestLength = -1;
void dfs(int node, int distance);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int V, nodeA, nodeB, weight;
cin >> V;
for (int i = 0; i < V; i++) {
cin >> nodeA;
while (true) {
cin >> nodeB;
if (nodeB == -1) {
break;
}
else {
cin >> weight;
pair<int, int> tempNode = { nodeB, weight };
graph[nodeA].emplace_back(tempNode);
}
}
}
dfs(1, 0);
for (int i = 1; i <= V; i++) {
visited[i] = false;
}
int startNode = furthestNode;
furthestNode = 0;
furthestLength = -1;
dfs(startNode, 0);
cout << furthestLength;
return 0;
}
void dfs(int node, int distance) {
if (!visited[node]) {
visited[node] = true;
if (distance > furthestLength) {
furthestLength = distance;
furthestNode = node;
}
for (auto nextNode : graph[node]) {
dfs(nextNode.first, distance + nextNode.second);
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
이 문제를 푸는 과정에서, 처음에는 std::stack을 이용하여 DFS를 진행하려고 했었다. 그런데 거리를 기록하는 것이 조금 귀찮아서 dfs 함수를 만들어서 풀어봤는데, 다행히 잘 통과하였다.
BFS나 DFS를 이용한 문제에서 보통 재귀함수를 이용하지 않았던 것은 함수 스택이 너무많이 쌓여서 에러를 뱉는 현상 때문에 피해왔는데, 이번에는 그런 문제는 딱히 없었던 것 같다. 문제가 되는 경우와 되지 않는 경우의 차이점이 무엇인지 언젠가 제대로 알아봐야 할 것 같다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1167